package middle;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class Solution_133 {
    private Node[] flags;
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        flags = new Node[101];
        Node newNode = new Node(node.val);
        dps(node, newNode);
        return newNode;
    }

    private void dps(Node old, Node newNode) {
        if (flags[old.val] != null) {
            return;
        }
        flags[old.val] = newNode;
        for (Node neighbor : old.neighbors) {
            Node node = flags[neighbor.val];
            if (node == null) {
                node = new Node(neighbor.val);
            }
            newNode.neighbors.add(node);
            dps(neighbor, node);
        }
    }

    public static void main(String[] args) {
        Solution_133 model = new Solution_133();
        Node node1 = new Node(1);
//        Node node2 = new Node(2);
//        Node node3 = new Node(3);
//        Node node4 = new Node(4);
//        node1.neighbors.add(node2);
//        node1.neighbors.add(node4);
//        node2.neighbors.add(node1);
//        node2.neighbors.add(node3);
//        node3.neighbors.add(node2);
//        node3.neighbors.add(node4);
//        node4.neighbors.add(node1);
//        node4.neighbors.add(node3);
        Node node = model.cloneGraph(node1);
        System.out.println();
    }

    static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
